//三合一
class TripleInOne {
public:
    //题意为 用一个数组实现三个栈结构
    //这些栈有标号 0号栈 1号栈 2号栈
    //这些栈有插入 删除 查看存在 判空等功能
    TripleInOne(int stackSize) 
        :_stacksize(stackSize)
    {
        s.resize(3*stackSize,0);
        for(int i=0;i<3;i++)
        {
            _index[i]=i*_stacksize;
        }
    }
    
    void push(int stackNum, int value) 
    {
        if(_index[stackNum] < (stackNum+1)*_stacksize)
        {
            s[_index[stackNum]++]=value;
        }

    }
    
    int pop(int stackNum) 
    {
        int res=-1;
        if(_index[stackNum] > stackNum*_stacksize)
        {
            _index[stackNum]--;
            res=s[_index[stackNum]];
        }
        return res;
    }
    //查看栈顶元素
    int peek(int stackNum) 
    {
        int res=-1;
        if(_index[stackNum] > stackNum*_stacksize)
        {
            res=s[_index[stackNum]-1];
        }
        return res;
    }
    
    bool isEmpty(int stackNum) 
    {
        if(_index[stackNum] == stackNum*_stacksize)
        {
            return true;
        }
        return false;
    }
private:
    vector<int> s;
    int _index[3]; //index[0] 表示0号栈的栈顶 index[1]表示1号栈的栈顶
    int _stacksize;
};
//用两个栈实现队列
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) 
    {
        _push.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() 
    {
        if(_out.empty())
        {
            while(!_push.empty())
            {
                _out.push(_push.top());
                _push.pop();
            }
        }
        int res=-1;
        if(!_out.empty())
        {
            res=_out.top();
            _out.pop();
        }
        return res;
    }
    
    /** Get the front element. */
    int peek() 
    {
        if(_out.empty())
        {
            while(!_push.empty())
            {
                _out.push(_push.top());
                _push.pop();
            }
        }
        int res=-1;
        if(!_out.empty())
        {
            res=_out.top();
        }
        return res;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() 
    {
        return _push.empty() && _out.empty();
    }
private:
    stack<int> _push;
    stack<int> _out;
};

//栈排序
class SortedStack {
public:
    // 设想 如果我的元素 是  7 6 5 3 2 1 这样的顺序入栈
    // 那么栈顶元素就是最小的 也就无需排序
    // 所以现在应该解决的问题是 当入栈的序列 出现了 后者大于前者的情况
    // primary栈中 7 5 3  此时入节点 4
    // 我们用helper栈 存 3 把4 放入 primary栈即可
    // 如果要拿最小值 就把helper栈的元素全部入primary栈
    // 成为 7 5 4 3 取top()即可
    // 所以 只需要在primary中进行插入操作
    // 并且在主栈中 让他成为一个降序栈 在helper栈中 让它成为升序栈
    // 从primary底部到primary顶部再到helper顶部再到helper底部 成为降序
    SortedStack() 
    {}
    
    void push(int val) 
    {
        //当前元素比我 helper栈里面的栈顶元素小
        //helper的栈顶元素应该给当前值让位置
        //所以让它去primary即可 因为primaty.top() >helper.top()
        //将他插入过去不会影响
        //
        while(!helper.empty() && helper.top() > val)
        {
            primary.push(helper.top());
            helper.pop();
        }
        //当前元素比primary.top()大
        //primaty.top()应该给他让位置 自己去helper栈即可
        while(!primary.empty() && primary.top() < val)
        {
            helper.push(primary.top());
            primary.pop();
        }
        //走到这里 要么位置已经腾好了 等待插入
        primary.push(val);
    }
    
    void pop() 
    {
        while(!helper.empty())
        {
            primary.push(helper.top());
            helper.pop();
        }
        if(!primary.empty()) primary.pop();

    }
    
    int peek() 
    {
        int res=-1;
        while(!helper.empty())
        {
            primary.push(helper.top());
            helper.pop();
        }
        if(!primary.empty()) res=primary.top();
        return res;
    }
    
    bool isEmpty() 
    {
        return primary.empty();

    }
    stack<int> primary;
    stack<int> helper;
};
//动物收容所
class AnimalShelf {
public:
    AnimalShelf() {
    }
    
    void enqueue(vector<int> animal) 
    {
        //animal[1]=0->cat 
        int id=animal[0];
        if(animal[1]==0) cat.push(id);
        else dog.push(id);

    }
    
    vector<int> dequeueAny() 
    {
        if(cat.empty()) return dequeueDog();
        else if(dog.empty()) return dequeueCat();
        else
        {
            if(cat.front() < dog.front()) return dequeueCat();
            else 
            {
                return dequeueDog();
            }
        }

    }
    
    vector<int> dequeueDog() 
    {
        if(dog.empty()) return {-1,-1};
        int id=dog.front();
        dog.pop();
        return {id,1};

    }
    
    vector<int> dequeueCat() 
    {
        if(cat.empty()) return {-1,-1};
        int id=cat.front();
        cat.pop();
        return {id,0};

    }
private:
    queue<int> cat;
    queue<int> dog;

};
